Subject: select loop prevention approach

From: Choon Lee <[email-masked]>
Date: Thu, 2 Sep 1993 10:28:06 -0700

The September AIW is approaching fast.  I hope that we can have 
some progress to show for by AIW (9/28).

Currently as I see it, we have two approaches. I'm only picking
the suggestions that has been proposed to this group, and
seconded by another member. If you think there are other viable 
proposals, do let me know. Also, I think that the consensus of
the group is that spanning tree is unsuitable for our purpose.

What I'd like all of us to do is to choose an approach to pursue,
since I don't think we have the bandwidth to refine both approaches.
Please email your selection to me or to the group. PLEASE VOICE YOUR OPINION.
Please send us your selection and comments by 9/13. That will 
leave us barely 2 weeks till AIW.

For those of you who have been following the discussions in this
group, you have seen the following mail excerpts. I am relisting
them for the benefits of others. The actual mail can be retrieved
from the aiw mail archive (aiw/maillogs/loopprevention.mail).

Approach #1: Heartbeat packets
------------------------------

[On 8/13, Scott Adams wrote]

>> What do people think of defining a "simple" protocol whereby each DLSw
>> periodically announces that it exists on each LAN it is connected to,
>> and who its DLSw partners are (call this a "This-is-Who-I-Know, or
>> TWIK packet).  If a DLSw receives one of these packets it compares the
>> other DLSw's partners to its own set of partners.  Using some
>> yet-to-be-defined algorithm it selects a non-intersecting set of
>> partners from the union of its partners and those reported by other
>> DLSwitches on the same LAN.  Those selected partners it alone will
>> communicate with.  The other DLSwitch(es) perform the same process,
>> selecting their own non-intersecting set of partners.  Each DLSw flags
>> as not useable the DLSw-DLSw connections it has to any partner not in
>> its list.  When it receives a broadcast LAN frame that's to be
>> propogated to DLSw partners, it doesn't send it out to those marked as
>> unuseable.  Likewise, if it receives from a "marked" partner an SSP
>> packet that would normally be broadcast to its local LAN(s), it would
>> not do so.
>> 
>> These DLSw partner sets would be updated, and aged, as a result of the
>> periodic broadcasts from DLSw.  If a DLSw stops broadcasting, then the
>> other DLSws, if connected with the same DLSw partners, would include
>> those partners that had been "owned" by the failed DLSw.  This might
>> take some time (if the TWIK period is 30 seconds, and the DLSws update
>> their partner sets each period, then it would require 30 seconds to
>> recover from a lost DLSw).
>> 
>> A simple algorithm for selecting the exclusive sets of partners is:
>> Each DLSw chooses those partners only it knows about.  All partners in
>> common with other DLSw are divided up evenly among the number of
>> DLSw's that know about them, with the fractions assigned to DLSw in
>> order of their IP addr host numbers.  For example, if there are 45
>> DLSw partners known by four different DLSw on the same LAN, then the
>> DLSw with the lowest host number would get the first twelve in the set
>> (the set of partners is ordered by IP address taken as an unsigned 32
>> bit number), the DLSw with the next lowest host number would get the
>> next 11, and so on.

[... and further,]

>> Good question.  In that situation my suggested solution doesn't cut
>> it.  But there is a way that it can be extended to fix the problem,
>> though.  TWIK frames broadcast on the LAN's contain the full IP
>> address of partner DLSw (DLSw A send a TWIK containting C's IP Addr, B
>> sends a TWIK with D's IP Addr, C send a TWIK w/ A's Addr and D send a
>> TWIK with B`s addr).  If receiving DLSw not only compare these partner
>> IP Addrs with their own partners, but also compare the IP Network
>> portion of these addrs (add the partner's subnet mask to the TWIK
>> packet, in addition to the IP addr), then each could detect that
>> another DLSw on the LAN has a partner on the same net as one of his
>> partners.  Then apply the same exclusion principle, but extended
>> slightly; ie: that only the DLSw with the lowest IP address can talk
>> with a partner DLSw on a given network.  In the new scenario you
>> describe, A and B would recognize that even though they don't share a
>> partner the partners they have are on the same network.  In that case
>> the DLSw with the lowest IP address would include its partner in its
>> partner group (say A has the lowest addr, then it would put C's addr
>> in its group).  B, recognizing that its partner is on the same net as
>> A's partner, and that its IP address is larger than A's, would not
>> include D in its partner goup (in fact, its group would be empty, thus
>> it wouldn't be able to talk to anyone).

(although I commented that IP network may not solve this problem, I
think that this scheme can be extended so it would work - i.e. we need
to work on it)

[On 8/23, Roy Dixon wrote]

>> This is Roy Dixon and I have been monitoring your exchange of notes on
>> the subject of loop prevention.  Although I have not had time to dig
>> through all the technical details, I believe that Scott Adams' proposal
>> is on the right track to a solution for this problem.
>> 
>> I agree that the use of the IEEE 802.1 spanning tree protocol does
>> not seem appropriate to the DLSw configuration.  Also, I like the
>> idea of introducing a LAN "heartbeat" function for DLSw (Scott's TWIK
>> packet).  This is very much akin to the mechanisms used by various
>> routing protocols for their router-to-router protocols (i.e., IS/IS Hello
>> in OSI protocols).  The heartbeat would be sent to a multicast address
>> assigned to DLSw and would use a well known Link SAP, yet to be defined.
>> 
>> The use of the heartbeat on the local LAN could also be beneficial for
>> solving the problem of establishing transport connections, a problem
>> under consideration by another SIGlet.
>> 
>>   o For example, the heartbeat could include parameters such as a region
>>   identifier associated with the bridged LAN.  This information would be
>>   predefined at each DLSW and the exchange of heartbeats would allow each
>>   DLSw to verify the configuration.  The region identifier would allow
>>   the mechanism used for setting up transport connections to understand
>>   that more than one DLSw is attached to the same bridged LAN.
>> 
>>   o Also, the heartbeat could include an identifier for the transport
>>   network, thereby allowing a single bridged LAN to be connected though
>>   data link switches to multiple transport networks.  In this case, the
>>   protocols for loop prevention would function independently for each
>>   transport network accessible from a given bridged LAN.
>> 
>> Now the details of this proposal have not been worked out completely, but
>> I wanted to let you know that I have been thinking along similar lines.
>> 
>> So to summarize:  if the heartbeat mechanism proves useful in solving the
>> loop-prevention problem, the addition of a region identifier and a
>> transport network identifier might then be used as an aid in establishing
>> and using the transport connections.
>> 

Approach #2: Modified TEST packet
---------------------------------

[On 8/19, Shannon Nix wrote]

>> In SRB: if the DLSW cloud is a virtual ring with a commonly administered 
>> ring number, then I believe both problems are addressed.
>> 
>> Transparent LAN segments adjacent to the DLSW cloud reintroduces the first
>> problem, loops.
>> 
>> AND
>> 
>> Parallel transparent forwarders - A DLSW combined with either another DLSW 
>> or pure transparent bridge providing parallel connectivity between a 
>> common adjacent transparent LAN segment and at least one other common LAN 
>> segment -  reintroduces the second problem, duplicate frames.
>> 
>> IF the only problem we were trying to solve were loop prevention - 
>> preventing broadcast traffic from traversing a DLSW cloud multiple times -, 
>> then I would propose the following:
>> 
>>    1)  We have a commonly administered virtual ring number for the DLSW 
>>        cloud for SRB ( this could be verified at capabilities exchange).
>> 
>>    2)  ROUTE EXPLORATION traverses the DLSW cloud as a CANUREACH.  
>> 
>>    3)  When ROUTE EXPLORATION exits the cloud, it is put onto the 
>>        a local LAN segment as a TEST frame.  
>> 
>>    4)  TEST frames can carry a field for data ( arbitrary user data 
>>        which should be echoed back in the TEST RSP).
>> 
>>    5)  Let's maintain a list of virtual ring, or cloud, numbers for the 
>>        DLSW clouds an exploration has traversed (just like a RIF!)
>> 
>>    6)  If you receive a TEST containing your virtual DLSW cloud number then
>>        discard it.
>> 
>>    7)  The CANUREACH must be enhanced to carry the virtual DLSW cloud
>>        list. This must be a list because DLSW clouds will be organized in
>>        "clusters" to get around the scalability issues.
>> 

[On 8/20, Choon Lee wrote]

>> I like this! With this scheme extended, I think we can achieve goal #1 (support
>> parallel DLSw paths). If we were to add also a tie-breaking element (maybe the IP
>> address) to the TEST frame, then when the DLSw receives a TEST frame with that 
>> virtual ring number in the data field, it knows that the TEST frame has gone 
>> through the DLSw switch before. With the IP address, it can decide whether it or
>> the other DLSw should respond with the ICANREACH when it gets the TEST response.
>> 
>> Do you think this would work? 
>> 
>> And for goal #2 (parallel DLSw and bridged path), if a DLSw node receives a TEST
>> frame that does not have the virtual ring number (frames going through the bridged
>> path won't), but has the same 3-tuple (SA,DA,SSAP) as a CANUREACH, then it can
>> again not respond with ICANREACH when a TEST response comes back.
>> 
>> Hey, this may work! I'm excited! 
>> BUT, do you think that it's OK that the TEST frame that's sent out to be different
>> (now contains different data) from being received? That shouldn't break anyone out
>> there, right? From RFC1434, it seems like XID flow happens after the DLSw has gone
>> into circuit established state. So we're now in fat city.

My opinion on these two approaches is that I think both are viable solutions.
The heartbeat packet (#1) approach need more work, but could be beneficial
for other uses (as Roy pointed out). However, I think there could be transient
period (during heartbeat interval) when packet flow is prohibited.

The modified TEST packet (#2) approach is simpler and it does not require 
any additional heartbeat packets. However it needs to modify the TEST packet.
Could that present a problem? Would it work for Netbios case?

Please let us know which approach you favor. 

Regards,
Choon Lee
3Com Corp.